// 字符串相乘,这是一道充分利用了模拟高精度的题目
// 题目要求: 将两个字符串里面的字符串转化成数字并相乘,但是不能使用接口的方式转化然后相乘
// 如果是这样的话,很多便捷的做题方式直接作废,只能将每个字符提取出来然后再相乘了

// 在这题中,我使用了竖式相乘法来求得答案,并且使用了一个顺序表来模拟高精度位

// 题目原理如下,选定一个字符串作为底,将其每位都乘上另外的一个字符串,可以参照竖式乘法的原理
// 关键在于,位数相乘之后的数字,怎么有效的进行存储并且能够在下一位相乘的时候,相应位数的数字能够全部相加进位,这样子才能够准确地得出答案

// 让我们回忆一下,我们在使用竖式乘法的时候,我们是怎么做运算的
// 以 10 x 20 为例子把: 
//   10
//   20 x
//----------
//   00
//  20  +
//----------
//  200

// 我们可以看到,将每位相乘之后,然后再将相应位的所有值相加,这样子就可以得出正确的得数
// 既然这样,那我们可以使用一个数组来模仿相对应的位,每次相乘的结果都可以通过对应的位进行相加以及进位,即可以得出正确的答案

class Solution {
public:
    string multiply(string num1, string num2) 
    {

        if (num1 == "0" || num2 == "0")
        {

            return "0" ;

        }

        int n = num1.size () ;

        int m = num2.size () ;

        vector <int> res (n + m , 0) ; // 乘法的性质,相乘最大位数不大于两数的位数相加,并且结果的位数只可能为: 两数位数相加 , 两数位数相加减一

        for (int i = n - 1 ; i >= 0 ; i--) // 这里模拟竖式相加的运算过程
        {

            for (int j = m - 1 ; j >= 0 ; j--) // 将一个字符串的各个位都与另外的字符串的每一位相乘
            {

                int k = (num1 [i] - '0') * (num2 [j] - '0') ;

                int sum = k + res [i + j + 1] ; // 从最高位开始记录,提取该位上面的数值加入计算当中

                res [i + j + 1] = sum % 10 ; // 模拟进位的过程

                res [i + j] += sum / 10 ;

            }
            
        }

        string s ;

        int index = res [0] == 0 ? 1 : 0 ; // 利用了乘法的性质,将每位的整数分别提取出来然后转为字符串

        while (index < m + n)
        {

            s.push_back (res [index]) ; // 使用尾插,前面就不会有0位出现

            index++ ;

        }

        for (auto &c : s)
        {

            c += '0' ;

        }

        return s ;
        
    }
};